/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package practice.v1;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:QuickSort.java v1.0 2018/8/11 上午11:42 LvJing Exp $
 */
public class QuickSort {

    public int[] quickSort(int[] arr) {
        if (arr == null || arr.length <= 1)
            return arr;

        /*
        快排思路为，跟冒泡一样是交换类排序，第一趟确认第一个元素最终的位置，即该元素左边的均小于它，右边的均大于它。后面依次对其左边和右边做同样
        确认第一个元素最终位置的事。
         */
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    private void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int middlePos = getMiddle(arr, low, high);
            quickSort(arr, low, middlePos - 1);
            quickSort(arr, middlePos + 1, high);
        }
    }

    private int getMiddle(int[] arr, int low, int high) {
        int middleValue = arr[low];
        while (low < high) {
            while (low < high && arr[high] > middleValue)
                high--;
            if (low != high)
                arr[low] = arr[high];

            while (low < high && arr[low] < middleValue)
                low++;
            if (low != high)
                arr[high] = arr[low];
        }
        arr[low] = middleValue;
        return low;
    }

    @Test
    public void test() {
        Random random = new Random();
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++)
            arr[i] = random.nextInt(100);
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
